package cn.com.colasoft.dataStructure;

/**
 * 有序数组
 * 向数组中添加数据,数组中的数据总是有序的
 * @author lizhitao
 * @date 2017/12/2
 * @since 1.0
 */
public class OrderedArray {

    /**
     * 有序数组
     */
    private long[] arrys;
    /**
     * 当前数组中存储的元素的个数
     */
    private int nElement;

    public OrderedArray(int max) {// max 数组最大存储的元素的个数
        arrys = new long[max];
        nElement = 0;
    }

    /**
     * 获取当前数组中存储的元素个数
     * @return
     */
    public int size() {
        return nElement;
    }

    /**
     * 插入数据(线性查找,添加)
     * @param value
     */
    public void insert(long value) {
        if (nElement == arrys.length) {
            throw new RuntimeException("Array is full. Not insert!");
        }
        int i;
        for (i = 0; i < nElement; i++) {
            // 找到了插入的索引位置
            if (value < arrys[i]) {
                break;
            }
        }
        // 移动索引位置后的所有的数据
        for (int j = nElement; j > i; j--) {
            arrys[j] = arrys[j-1];
        }
        arrys[i] = value;
        nElement++;
    }

    /**
     * 删除数据项(二分查找删除)
     * @param value
     * @return
     */
    public boolean delete(long value) {
        int index = find(value);
        if (index != -1) { // 找到了删除值的索引位置
            for (int i = index; i < nElement; i++) {
                arrys[i] = arrys[i+1];
            }
            nElement--;
            return true;
        }
        return false;
    }

    /**
     * 二分查找数据项的位置
     * @param searchKey 查找的值
     * @return 返回数据索引位置,如果未查找到数据则返回-1
     */
    public int find(long searchKey) {
        // 当前最小索引位置
        int minIndex = 0;
        // 当前最大的索引位置
        int maxIndex = nElement - 1;
        // 当前中间的索引位置
        while (true) {
            int midIndex = (minIndex + maxIndex) / 2;
            if (searchKey == arrys[midIndex]) {
                return midIndex;
            } else if (minIndex > maxIndex) {
                return -1;
            } else if (searchKey > arrys[midIndex]) {
                // 注意要剔除当前mid索引位置
                 minIndex = midIndex + 1;
            } else if (searchKey < arrys[midIndex]) {
                // 注意要剔除当前mid索引位置
                maxIndex = midIndex - 1;
            }
        }
    }

    /**
     * 显示出数组所有数据项
     */
    public void display() {
        System.out.print("[");
        for (int i = 0; i < nElement; i++) {
            System.out.print(arrys[i] + ",");
        }
        System.out.print("]\n");
    }

    public static void main(String[] args) {
        OrderedArray orderedArray = new OrderedArray(10);
        orderedArray.insert(20);
        orderedArray.insert(19);
        orderedArray.insert(17);
        orderedArray.insert(40);
        orderedArray.display();

        orderedArray.delete(19);

        orderedArray.display();
    }
}
